home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / cmds / pmake / customs / election.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-11-15  |  17.3 KB  |  651 lines
  1. /*-
  2.  * election.c --
  3.  *    This functions in this file are responsible for performing the
  4.  *    election algorithm used by the customs daemons.
  5.  *
  6.  * Copyright (c) 1988, 1989 by the Regents of the University of California
  7.  * Copyright (c) 1988, 1989 by Adam de Boor
  8.  * Copyright (c) 1989 by Berkeley Softworks
  9.  *
  10.  * Permission to use, copy, modify, and distribute this
  11.  * software and its documentation for any non-commercial purpose
  12.  * and without fee is hereby granted, provided that the above copyright
  13.  * notice appears in all copies.  The University of California,
  14.  * Berkeley Softworks and Adam de Boor make no representations about
  15.  * the suitability of this software for any purpose.  It is provided
  16.  * "as is" without express or implied warranty.
  17.  */
  18. #ifndef lint
  19. static char *rcsid =
  20. "$Id: election.c,v 1.13 89/11/14 13:46:00 adam Exp $ SPRITE (Berkeley)";
  21. #endif lint
  22.  
  23. #include    "customsInt.h"
  24. #include    "log.h"
  25. #include    <sys/file.h>
  26. #include    <sys/stat.h>
  27. #include    <errno.h>
  28. #include    <arpa/inet.h>
  29.  
  30. struct sockaddr_in   masterAddr;
  31.  
  32. /*-
  33.  * bool_t
  34.  * CustomsCampaign ()
  35.  *
  36.  * Broadcast by an sca that wants to become the master. Response is TRUE
  37.  * if someone else is also trying to become the master. FALSE if someone else
  38.  * already is the master.
  39.  */
  40.  
  41. /*-
  42.  * void
  43.  * CustomsNewMaster()
  44.  *
  45.  * Broadcast by the new mca to all scas to inform them that a new master
  46.  * has been elected and the receiving sca should restart.
  47.  */
  48.  
  49. static enum {
  50.     HAVE_NONE,             /* No response */
  51.     HAVE_CONFLICT,          /* Other agent also campaigning */
  52.     HAVE_MASTER            /* Master exists */
  53. }                       campaignResponse;
  54.  
  55. typedef struct sockaddr_in  SockAddr;
  56. typedef struct in_addr        InetAddr;
  57.  
  58. /*
  59.  * A variable to track where we are in an election.
  60.  */
  61. enum {
  62.     NONE,           /* No election is taking place */
  63.     WAITING,        /* We've ok'd someone else's petition, now waiting for
  64.              * NewMaster message */
  65.     PETITIONING,    /* We've asked to become the master. Waiting for
  66.              * responses */
  67.     BACKOFF,        /* Our petition was refused. Waiting to try again. */
  68.     REGISTERING,    /* Registering with the new master */
  69. } ElectionState;
  70.  
  71. InetAddr          lastPetition;    /* Address of last sca whose petition we
  72.                  * accepted. Valid only if WAITING */
  73. Rpc_Event          waitEvent;    /* Event for returning to NONE state after
  74.                  * WAITING */
  75.  
  76. struct timeval      backOff;      /* Timeout for exponential backoff */
  77.  
  78. long              elect_Token;    /* Token for our network. Set at startup */
  79.  
  80. static void       ElectCampaign(),
  81.           ElectNewMaster(),
  82.           ElectForce();
  83. /*-
  84.  *-----------------------------------------------------------------------
  85.  * Elect_Init --
  86.  *    Initialize this module.
  87.  *
  88.  * Results:
  89.  *    None.
  90.  *
  91.  * Side Effects:
  92.  *    The random number generator is randomized, ElectionState set to
  93.  *    NONE, lastPetition set to INADDR_ANY and the election RPC servers
  94.  *    installed on the main udp socket.
  95.  *
  96.  *-----------------------------------------------------------------------
  97.  */
  98. void
  99. Elect_Init ()
  100. {
  101.     struct timeval t;
  102.  
  103.     /*
  104.      * Randomize for exponential backoff
  105.      */
  106.     gettimeofday(&t, (struct timezone *)NULL);
  107.     srandom((int)(getpid() + gethostid() + t.tv_sec + t.tv_usec));
  108.     
  109.     ElectionState = NONE;
  110.     lastPetition.s_addr = INADDR_ANY;
  111.  
  112.     Rpc_ServerCreate(udpSocket, (Rpc_Proc)CUSTOMS_CAMPAIGN, ElectCampaign,
  113.              Rpc_SwapLong, Rpc_SwapLong, (Rpc_Opaque)0);
  114.     Rpc_ServerCreate(udpSocket, (Rpc_Proc)CUSTOMS_NEWMASTER, ElectNewMaster,
  115.              Rpc_SwapLong, Rpc_SwapNull, (Rpc_Opaque)0);
  116.     Rpc_ServerCreate(udpSocket, (Rpc_Proc)CUSTOMS_ELECT, ElectForce,
  117.              Rpc_SwapNull, Rpc_SwapNull, (Rpc_Opaque)0);
  118. }
  119.  
  120. /*-
  121.  *-----------------------------------------------------------------------
  122.  * ElectBackOffDone --
  123.  *    Called when the backOff time has expired. Sets the boolean to
  124.  *    which it is pointed to TRUE.
  125.  *
  126.  * Results:
  127.  *    TRUE.
  128.  *
  129.  * Side Effects:
  130.  *    'done' in ElectBackOff is set TRUE.
  131.  *
  132.  *-----------------------------------------------------------------------
  133.  */
  134. static Boolean
  135. ElectBackOffDone(donePtr)
  136.     Boolean *donePtr;
  137. {
  138.     *donePtr = TRUE;
  139.     return(TRUE);
  140. }
  141.  
  142. /*-
  143.  *-----------------------------------------------------------------------
  144.  * ElectBackOff --
  145.  *    Delay for a random amount of time that increases exponentially
  146.  *    each time this is called. If backOff is 0, a new random time
  147.  *    is selected, else the old time is multiplied by 2.
  148.  *
  149.  * Results:
  150.  *    None.
  151.  *
  152.  * Side Effects:
  153.  *    We delay for a while, handling requests from clients and other
  154.  *    agents as gracefully as possible.
  155.  *
  156.  *-----------------------------------------------------------------------
  157.  */
  158. static void
  159. ElectBackOff()
  160. {
  161.     Rpc_Event      backEvent;
  162.     Boolean       done;
  163.     
  164.     if ((backOff.tv_sec == 0) && (backOff.tv_usec == 0)) {
  165.     int t;
  166.  
  167.     /*
  168.      * 1,000,000 ~ 2^20, so take the low twenty bits for microseconds
  169.      * and the next 3 bits for seconds to get the new backoff amount.
  170.      */
  171.     t = random();
  172.     backOff.tv_usec = t & 0xfffff;
  173.     backOff.tv_sec = (t >> 20) & 7;
  174.     } else {
  175.     /*
  176.      * Double the delay.
  177.      */
  178.     backOff.tv_usec *= 2;
  179.     backOff.tv_sec *= 2;
  180.     }
  181.     /*
  182.      * Normalize the time value
  183.      */
  184.     while (backOff.tv_usec > 1000000) {
  185.     backOff.tv_sec += 1;
  186.     backOff.tv_usec -= 1000000;
  187.     }
  188.  
  189.     done = FALSE;
  190.     backEvent = Rpc_EventCreate(&backOff, ElectBackOffDone, (Rpc_Opaque)&done);
  191.     if (verbose) {
  192.     printf ("waiting %d.%06d seconds\n", backOff.tv_sec, backOff.tv_usec);
  193.     }
  194.  
  195.     while (!done) {
  196.     Rpc_Wait();
  197.     }
  198.     Rpc_EventDelete(backEvent);
  199. }
  200.  
  201. /*-
  202.  *-----------------------------------------------------------------------
  203.  * ElectCampaignResponse --
  204.  *    Catch the response to a CAMPAIGN broadcast. Accepts responses
  205.  *    until one comes from the current master.
  206.  *
  207.  * Results:
  208.  *    None.
  209.  *
  210.  * Side Effects:
  211.  *    If the response is FALSE (master saying no), masterAddr is
  212.  *    overwritten and campaignResponse is set to HAVE_MASTER. Else,
  213.  *    campaignResponse is set to HAVE_CONFLICT.
  214.  *
  215.  *-----------------------------------------------------------------------
  216.  */
  217. /*ARGSUSED*/
  218. static Boolean
  219. ElectCampaignResponse(from, len, response)
  220.     struct sockaddr_in    *from;        /* Source of response */
  221.     int                  len;        /* Length of response */
  222.     Boolean           *response;  /* Response value */
  223. {
  224.     if (ntohs(from->sin_port) != udpPort) {
  225.     /*
  226.      * If response from a non-agent, ignore it
  227.      */
  228.     return(False);
  229.     } else if (*response) {
  230.     if (campaignResponse == HAVE_NONE) {
  231.         campaignResponse = HAVE_CONFLICT;
  232.     }
  233.     } else if (campaignResponse == HAVE_MASTER) {
  234.     if (from->sin_addr.s_addr != masterAddr.sin_addr.s_addr) {
  235.         /*
  236.          * If more than one agent is claiming to be the master, inform
  237.          * the first one we met of the other one's address. It'll take
  238.          * care of the rest. Not sure how to actually use this, since
  239.          * broadcasting isn't multi-threaded enough -- will get responses
  240.          * back and lose them while this call is in progress.
  241.          */
  242.         printf("Warning: duplicate master at %s\n",
  243.            InetNtoA(from->sin_addr));
  244.         (void) Rpc_Call(udpSocket, &masterAddr, (Rpc_Proc)CUSTOMS_CONFLICT,
  245.                 sizeof(struct sockaddr_in), (Rpc_Opaque)from,
  246.                 0, (Rpc_Opaque)0,
  247.                 CUSTOMSINT_NRETRY, &retryTimeOut);
  248.     }
  249.     } else {
  250.     campaignResponse = HAVE_MASTER;
  251.     masterAddr = *from;
  252.     return (True);
  253.     }
  254.     /*
  255.      * We want to broadcast for the entire time....
  256.      */
  257.     return (False);
  258. }
  259.  
  260. /*-
  261.  *-----------------------------------------------------------------------
  262.  * Elect_GetMaster --
  263.  *    Elect a new master using a broadcast election algorithm. When
  264.  *    this function returns, a new master will have been elected and its
  265.  *    address stored in masterAddr. If we are that new master, amMaster
  266.  *    will be TRUE.
  267.  *
  268.  * Results:
  269.  *    None.
  270.  *
  271.  * Side Effects:
  272.  *    masterAddr is overwritten and amMaster may be changed.
  273.  *
  274.  *-----------------------------------------------------------------------
  275.  */
  276. void
  277. Elect_GetMaster ()
  278. {
  279.     Boolean            conflict;           /* Space for Campaign response */
  280.     Rpc_Stat          rstat;                /* Status of broadcast */
  281.     SockAddr          broadcast;          /* Address to which to broadcast */
  282.  
  283.     timerclear(&backOff);
  284.     broadcast.sin_family = AF_INET;
  285.     broadcast.sin_port = htons(udpPort);
  286.     broadcast.sin_addr.s_addr = htons(INADDR_ANY);
  287.     
  288.     while (1) {
  289.     if (verbose) {
  290.         printf("Petitioning...");
  291.     }
  292.     ElectionState = PETITIONING;
  293.     campaignResponse = HAVE_NONE;
  294.     rstat = Rpc_Broadcast(udpSocket, &broadcast,
  295.                   (Rpc_Proc)CUSTOMS_CAMPAIGN,
  296.                   sizeof(elect_Token), (Rpc_Opaque)&elect_Token,
  297.                   sizeof(conflict), (Rpc_Opaque)&conflict,
  298.                   3, &retryTimeOut,
  299.                   ElectCampaignResponse);
  300.     switch(rstat) {
  301.         case RPC_SUCCESS:
  302.         /*
  303.          * Someone objected to our becoming master.
  304.          */
  305.         if (campaignResponse == HAVE_CONFLICT) {
  306.             /*
  307.              * Objected because it was also trying to become the
  308.              * master. Do exponential backoff in an attempt not
  309.              * to conflict again.
  310.              */
  311.             if (verbose) {
  312.             printf("CONFLICT: backing off\n");
  313.             }
  314.             ElectionState = BACKOFF;
  315.             ElectBackOff();
  316.             break;
  317.         } else if (campaignResponse == HAVE_MASTER) {
  318.             /*
  319.              * Objected because it was already the master.
  320.              * Attempt to contact the agent. If we manage to do so,
  321.              * register with it. If that fails, try again...
  322.              */
  323.             if (verbose) {
  324.             printf("REFUSED: Contacting new master...");
  325.             }
  326.             ElectionState = NONE;
  327.             rstat = Rpc_Call(udpSocket, &masterAddr,
  328.                      (Rpc_Proc)CUSTOMS_REG,
  329.                      regPacketLen, (Rpc_Opaque)regPacket,
  330.                      0, (Rpc_Opaque)0,
  331.                      CUSTOMSINT_NRETRY, &retryTimeOut);
  332.             if (rstat == RPC_SUCCESS) {
  333.             if (verbose) {
  334.                 printf ("New master: %s\n",
  335.                     InetNtoA(masterAddr.sin_addr));
  336.             }
  337.             return;
  338.             } else if (verbose) {
  339.             printf("GetMaster: contacting new: %s\n",
  340.                    Rpc_ErrorMessage(rstat));
  341.             }
  342.             break;
  343.         }
  344.         /*FALLTHRU*/
  345.         case RPC_TIMEDOUT:
  346.         /*
  347.          * Noone responded. We are the master.
  348.          */
  349.         masterAddr = localAddr;
  350.         if (verbose) {
  351.             printf("No one responded: Accepting mastery\n");
  352.         }
  353.         /*
  354.          * Become the master -- it will send out the NEWMASTER call
  355.          * when it's ready.
  356.          */
  357.         ElectionState = NONE;
  358.         amMaster = TRUE;
  359.         MCA_Init();
  360.         Log_Send(LOG_NEWMASTER, 1, xdr_sockaddr_in, &localAddr);
  361.  
  362.         return;
  363.         default: {
  364.         extern int errno;
  365.         extern char *sys_errlist[];
  366.  
  367.         printf("Rpc_Broadcast: %s\n", sys_errlist[errno]);
  368.         printf("CUSTOMS_CAMPAIGN: %s\n", Rpc_ErrorMessage(rstat));
  369.         break;
  370.         }
  371.     }
  372.     }
  373. }
  374.  
  375. /*-
  376.  *-----------------------------------------------------------------------
  377.  * Elect_InProgress --
  378.  *    Tell if an election is in progress.
  379.  *
  380.  * Results:
  381.  *    TRUE if there's one going. FALSE otherwise.
  382.  *
  383.  * Side Effects:
  384.  *    None.
  385.  *
  386.  *-----------------------------------------------------------------------
  387.  */
  388. Boolean
  389. Elect_InProgress ()
  390. {
  391.     return ((ElectionState == PETITIONING) || (ElectionState == BACKOFF));
  392. }
  393.     
  394.  
  395. /*-
  396.  *-----------------------------------------------------------------------
  397.  * ElectClearWait --
  398.  *    Return from WAITING to NONE state. Callback for ElectCampaign.
  399.  *
  400.  * Results:
  401.  *    FALSE.
  402.  *
  403.  * Side Effects:
  404.  *    ElectionState is set to NONE if it was WAITING.
  405.  *
  406.  *-----------------------------------------------------------------------
  407.  */
  408. static Boolean
  409. ElectClearWait()
  410. {
  411.     if (ElectionState == WAITING) {
  412.     ElectionState = NONE;
  413.     }
  414.     Rpc_EventDelete(waitEvent);
  415.     waitEvent = (Rpc_Event)0;
  416.     return(FALSE);
  417. }
  418. /*-
  419.  *-----------------------------------------------------------------------
  420.  * ElectCampaign --
  421.  *    Stub for CUSTOMS_CAMPAIGN call. To allow for an heterogenous
  422.  *    network, this stub only pays attention to calls for which the
  423.  *    data is elect_Token. elect_Token is set at startup and allows a
  424.  *    network to be partitioned into subnets.
  425.  *
  426.  *    If we have nothing to say, we don't respond at all. We can do that
  427.  *    now there's only the campaigning agent waiting.
  428.  *
  429.  * Results:
  430.  *    None.
  431.  *
  432.  * Side Effects:
  433.  *    A response will be generated if we are (a) campaigning ourselves or
  434.  *     (b) we are the master.
  435.  *
  436.  *-----------------------------------------------------------------------
  437.  */
  438. static void
  439. ElectCampaign(from, msg, len, data)
  440.     struct sockaddr_in    *from;
  441.     Rpc_Message          msg;
  442.     int                  len;
  443.     int                  *data;
  444. {
  445.     Boolean           response;
  446.     
  447.     if (verbose) {
  448.     printf("Received CAMPAIGN from %d@%s: ", ntohs(from->sin_port),
  449.            InetNtoA(from->sin_addr));
  450.     }
  451.     if (ntohs(from->sin_port) != udpPort) {
  452.     return;
  453.     }
  454.     if (Local(from)) {
  455.     if (verbose) {
  456.         printf("talking to myself, again...\n");
  457.     }
  458.     } else if ((len == sizeof(int)) && (*data == elect_Token)) {
  459.     /*
  460.      * If machine has same byte-order as we do, then we can play
  461.      * master/slave with it...
  462.      */
  463.     if (amMaster) {
  464.         if (verbose) {
  465.         printf("return(FALSE)\n");
  466.         }
  467.         response = FALSE;
  468.         Rpc_Return(msg, sizeof(response), (Rpc_Opaque)&response);
  469.     } else if (ElectionState == PETITIONING) {
  470.         if (verbose) {
  471.         printf ("return(TRUE)\n");
  472.         }
  473.         response = TRUE;
  474.         Rpc_Return(msg, sizeof(response), (Rpc_Opaque)&response);
  475.     } else if ((ElectionState == WAITING) &&
  476.            (lastPetition.s_addr != from->sin_addr.s_addr))
  477.     {
  478.         /*
  479.          * If someone else was campaigning, we refuse to let
  480.          * this agent become the master. This is in case the
  481.          * campaigning one missed the broadcast somehow.
  482.          */
  483.         if (verbose) {
  484.         printf ("return (TRUE) -- conflict with %s\n",
  485.             InetNtoA(lastPetition));
  486.         }
  487.         response = TRUE;
  488.         Rpc_Return(msg, sizeof(response),
  489.                (Rpc_Opaque)&response);
  490.     } else {
  491.         /*
  492.          * It's ok for this agent to become master, as far as we're
  493.          * concerned. Because petitions are broadcast at startup,
  494.          * we don't want to stay in the WAITING state forever, or
  495.          * we'll have to wait for everyone to timeout before we can
  496.          * elect a master (everyone's petitions will be refused
  497.          * until then) and that isn't good. So we set an event for
  498.          * twenty seconds from now to return to the NONE state.
  499.          */
  500.         struct timeval waitTimeout;
  501.         
  502.         if (verbose) {
  503.         printf("OK\n");
  504.         }
  505.         if (ElectionState == NONE) {
  506.         /*
  507.          * Only alter the state if no election was in progress.
  508.          * We must allow petitions if ElectionState == BACKOFF,
  509.          * but if we set ElectionState to WAITING, the Avail
  510.          * module might try to send to a non-existent master...
  511.          */
  512.         ElectionState = WAITING;
  513.         }
  514.         lastPetition = from->sin_addr;
  515.         
  516.         waitTimeout.tv_sec = 10;
  517.         waitTimeout.tv_usec = 0;
  518.         if (waitEvent != (Rpc_Event)NULL) {
  519.         Rpc_EventDelete(waitEvent);
  520.         }
  521.         waitEvent = Rpc_EventCreate(&waitTimeout, ElectClearWait,
  522.                     (Rpc_Opaque)0);
  523.     }
  524.     } else if (verbose) {
  525.     printf("not my type\n");
  526.     }
  527. }
  528.  
  529. /*-
  530.  *-----------------------------------------------------------------------
  531.  * ElectNewMaster --
  532.  *    Stub for the CUSTOMS_NEWMASTER broadcast call.
  533.  *
  534.  * Results:
  535.  *    None.
  536.  *
  537.  * Side Effects:
  538.  *    If we currently are the master, cancels our mastery.
  539.  *
  540.  *-----------------------------------------------------------------------
  541.  */
  542. static void
  543. ElectNewMaster(from, msg, len, data)
  544.     struct sockaddr_in    *from;
  545.     Rpc_Message          msg;
  546.     int                  len;
  547.     int                  *data;
  548. {
  549.     Rpc_Stat          rstat;
  550.  
  551.     if (verbose) {
  552.     printf ("Received NEWMASTER from %d@%s: ", ntohs(from->sin_port),
  553.         InetNtoA(from->sin_addr));
  554.     }
  555.     if (ntohs(from->sin_port) != udpPort) {
  556.     time_t    now;
  557.  
  558.     time(&now);
  559.     if (verbose) {
  560.         printf("wrong port number -- %s", ctime(&now));
  561.     } else {
  562.         printf("Bogus NEWMASTER from %d@%s -- %s", ntohs(from->sin_port),
  563.            InetNtoA(from->sin_addr), ctime(&now));
  564.     }
  565.     return;
  566.     }
  567.     if ((ElectionState == NONE) || (ElectionState == WAITING)) {
  568.     if (Local(from)) {
  569.         Rpc_Return(msg, 0, (Rpc_Opaque)0);
  570.         if (verbose) {
  571.         printf ("talking to myself, again...\n");
  572.         }
  573.     } else if ((len == sizeof(int)) && (*data == elect_Token)) {
  574.         Rpc_Return(msg, 0, (Rpc_Opaque)0);
  575.         if (amMaster) {
  576.         if (verbose) {
  577.             printf ("cancelling mastery\n");
  578.         }
  579.         MCA_Cancel();
  580.         amMaster = FALSE;
  581.         } else if (verbose) {
  582.         putchar('\n');
  583.         }
  584.         masterAddr = *from;
  585.         ElectionState = REGISTERING;
  586.         rstat = Rpc_Call(udpSocket, &masterAddr, (Rpc_Proc)CUSTOMS_REG,
  587.                  regPacketLen, (Rpc_Opaque)regPacket,
  588.                  0, (Rpc_Opaque)0,
  589.                  CUSTOMSINT_NRETRY, &retryTimeOut);
  590.  
  591.         if (rstat != RPC_SUCCESS) {
  592.         printf ("Registering with new master: %s\n",
  593.             Rpc_ErrorMessage(rstat));
  594.         Elect_GetMaster();
  595.         }
  596.         ElectionState = NONE;
  597.     } else if (verbose) {
  598.         printf ("not my type\n");
  599.     }
  600.     } else if (verbose) {
  601.     printf ("ignored\n");
  602.     }
  603. }
  604. /*-
  605.  *-----------------------------------------------------------------------
  606.  * ElectForce --
  607.  *    Force an election, cancelling our mastery, if we're the master.
  608.  *
  609.  * Results:
  610.  *    Nothing.
  611.  *
  612.  * Side Effects:
  613.  *    
  614.  *-----------------------------------------------------------------------
  615.  */
  616. static void
  617. ElectForce(from, msg, len, data)
  618.     struct sockaddr_in    *from;
  619.     Rpc_Message          msg;
  620.     int                  len;
  621.     int                  *data;
  622. {
  623.     if (verbose) {
  624.     printf("ELECT received from %d@%s...",
  625.            ntohs(from->sin_port), InetNtoA(from->sin_addr));
  626.     }
  627.     
  628.     /*
  629.      * Signal our acceptance
  630.      */
  631.     Rpc_Return(msg, 0, (Rpc_Opaque)0);
  632.     
  633.     /*
  634.      * If we're the master, cancel it before starting the election.
  635.      */
  636.     if (amMaster) {
  637.     if (verbose) {
  638.         printf ("cancelling mastery\n");
  639.     }
  640.     MCA_Cancel();
  641.     amMaster = FALSE;
  642.     } else if (verbose) {
  643.     putchar('\n');
  644.     }
  645.  
  646.     /*
  647.      * Now force an election.
  648.      */
  649.     Elect_GetMaster();
  650. }
  651.